Palindrome

• A sequence of characters that read the same, forwards and backwards.
• There are 2 types of palindromes:
  • Odd palindromes: Have a single character in the middle, e.g: "civic"
  • Even palindromes: Have two characters constitute the middle, both of which must be the same, e.g: "noon"
• Palindromes expand around their center
  • Smaller palindromes make up larger palindrome
  • E.g: "eve" is a palindrome that is inside of "level"
  • Conversely, if you removed the starting and ending characters you'd be left with the smaller, single-character palindrome

Approach:

• The most common approach when solving palindromes problem
  • Use [[3. Two Pointer]] from both end and check difference
  • Use the homogeneous properties and validate palindromes around the center instead of from 2 ends

https://leetcode.com/problems/valid-palindrome-ii

• Simple 2 pointer checking from both ends

def validPalindrome(self, s: str) -> bool:
    left, right = 0, len(s) - 1

    while left <= right:
        if s[left] != s[right]:
            s1 = s[left:right]
            s2 = s[left+1: right+1]

            return s1 == s1[::-1] or s2 == s2[::-1]

        left += 1
        right -= 1
    
    return True

https://leetcode.com/problems/palindromic-substrings

• Direct application of the homogeneous property

def countSubstrings(self, s: str) -> int:
    res = 0

    for i in range(len(s)):
        left = right = i

        while left >= 0 and right < len(s) and s[left] == s[right]:
            res += 1
            left -= 1
            right += 1
        
        left = i
        right = i+1
        while left >= 0 and right < len(s) and s[left] == s[right]:
            res += 1
            left -= 1
            right += 1 
    
    return res

https://leetcode.com/problems/longest-palindromic-substring

• Same as above
• Using the homogeneous property

def longestPalindrome(self, s: str) -> str:
    res = ""

    for i in range(len(s)):
        left = right = i

        while left >= 0 and right < len(s) and s[left] == s[right]:
            if right - left + 1 > len(res):
                res = s[left:right+1]
            left -= 1
            right += 1

        left = i
        right = i+1
        while left >= 0 and right < len(s) and s[left] == s[right]:
            if right - left + 1 > len(res):
                res = s[left:right+1]
            left -= 1
            right += 1
    
    return res

https://leetcode.com/problems/valid-palindrome-iv

• Same as above
• Using the homogeneous property

def makePalindrome(self, s: str) -> bool:
    def checkEven():
        mid = len(s) // 2
        left, right = mid-1, mid
        changeCount = 0

        while left >= 0 and right < len(s):
            if s[left] != s[right]:
                if changeCount >= 2:
                    return False
                changeCount += 1
            left -= 1
            right += 1

        return True

    def checkOdd():
        mid = len(s) // 2
        left, right = mid, mid
        changeCount = 0

        while left >= 0 and right < len(s):
            if s[left] != s[right]:
                if changeCount >= 2:
                    return False
                changeCount += 1
            left -= 1
            right += 1

        return True

    if len(s) % 2 == 0:
        return checkEven()
    else:
        return checkOdd()